package qjc.i_图论;

import java.util.ArrayList;
import java.util.List;

public class i3_课程表 {
    /**
     * 解题思路：
     * 本题判断是否可以完成所有课程（课程表问题），本质上是判断有向图中是否存在环。
     * 每门课程是一个节点，先修关系（[a, b] 表示 b 是 a 的先修课）构成一条从 b → a 的有向边。
     * 若图中存在环（如 A→B→A），则无法完成所有课程。
     * <p>
     * 核心思想：拓扑排序 + DFS 染色法判环
     * <p>
     * 1. 建图：使用邻接表 edges 存储每个节点的出边（即修完当前课程后可修的课程）；
     * 2. 使用 visited 数组标记节点状态：
     * - 0：未访问
     * - 1：正在访问（在当前 DFS 路径中）
     * - 2：已访问且无环（安全节点）
     * 3. 对每个未访问的节点进行 DFS：
     * - 进入节点时标记为 1（正在访问）；
     * - 遍历其所有邻接节点：
     * - 若邻接节点未访问，递归访问；
     * - 若邻接节点状态为 1，说明遇到了当前路径上的节点，存在环，返回 false；
     * - 回溯时标记为 2（已处理完成，无环）；
     * 4. 若所有节点都处理完且未发现环，则返回 true。
     * <p>
     * 关键点：
     * - 用三色标记法（0/1/2）高效判断有向图中是否存在环；
     * - 状态 1 表示“在递归栈中”，是检测环的关键；
     * - 使用全局变量 valid 控制提前终止；
     * - 需对所有节点进行 DFS，因为图可能不连通。
     * <p>
     * 时间复杂度 O(n + m)，n 为课程数，m 为先修关系数；
     * 空间复杂度 O(n + m)，邻接表和递归栈。
     *
     * @param numCourses
     * @param prerequisites
     * @return
     */
    List<List<Integer>> res;
    int[] visited;
    boolean valid;

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        res = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            res.add(new ArrayList<>());
        }
        visited = new int[numCourses];
        for (int[] i : prerequisites) {
            res.get(i[1]).add(i[0]);
        }
        valid = true;
        for (int i = 0; i < numCourses && valid; i++) {
            if (visited[i] == 0) {
                dfs(i);
            }
        }
        return valid;
    }

    private void dfs(int u) {
        visited[u] = 1;
        for (int v : res.get(u)) {
            if (visited[v] == 0) {
                dfs(v);
                if (!valid) {
                    return;
                }
            } else if (visited[v] == 1) {
                valid = false;
                return;
            }
        }
        visited[u] = 2;
    }
}
